#include <vector>
#include<array>

class Solution {
public:
    std::vector<int> sortArrayByParityII(std::vector<int>& nums) {
        int n = nums.size();
        int o = 0;
        int e = 1;
        while (o<n&&e<n)
        {
            if (nums[n-1]%2 ==0)
            {
                swap(nums,o,n-1);
                o+=2;
            }else
            {
                swap(nums,e,n-1);
                e+=2;
            }
        }
        return nums;
    }
    void swap(std::vector<int>& nums,int i,int j)
    {
        int d = nums[i];
        nums[i]= nums[j];
        nums[j]=d;
    }
};